package arithmetic.demo5;


import java.util.Arrays;
import java.util.Scanner;

/**
 * 贪心_最长回文子串
 */

class Solution {
    public int longestPalindrome(String s) {
        int n = s.length(); 
        int[] hash = new int[100];
        char[] chs = s.toCharArray();


        // 统计个数
        for(int i = 0; i < n; i++) {
            hash[chs[i] - 'A']++;
        }

        // 统计双字符的个数
        int ret= 0;
        for(int i =0; i < 100; i++) {
            ret += hash[i] / 2 * 2;
        }

        // 找出奇数个
        for(int i =0; i < 100; i++) {
            if(hash[i] % 2 == 1) return ret + 1;
        }
        

        return ret ;
    }
}


/**
 * 题目： 贪心_增减字符串匹配
 */
class Solution1 {
    public int[] diStringMatch(String s) {
        int n = s.length();
        int left = 0, right = n ;
        int[] ret = new int[n+1];

        for(int i = 0; i < n; i++) {
            // 增加的情况就填入小的元素
            if(s.charAt(i) == 'I') {
                ret[i] = left++;
            } else {
                // 减少点情况就填入大的元素
                ret[i] = right--;
            }
        }

        // 把最后一个元素进行补充
        ret[n] = left;

        return ret;
    }
}


/**
 * 题目: 贪心_分发饼干
 */


class Solution2 {
    public int findContentChildren(int[] g, int[] s) {
        // 进行排序
        Arrays.sort(g);
        Arrays.sort(s);
        int n1 = g.length, n2= s.length;

        // 从小开始分配即可
        int i = 0, j = 0;
        while(i < n1 && j < n2) {
            if(s[j] >= g[i]) {
                j++;
                i++;
            } else {
                j++;
            }
        }

        return i;
    }
}


/**
 * 题目:  贪心_最优除法
 */

class Solution3 {
    public String optimalDivision(int[] nums) {
        int n = nums.length ;

        // 特殊情况处理
        if(n== 1) return nums[0] + "";
        if(n== 2) return nums[0] + "/" + nums[1];

        // 加入前面的
        StringBuilder ret = new StringBuilder((nums[0] + "/("));



        // 加入中间的
        for(int i = 1; i < n-1; i++) {
            ret.append(nums[i] + "/");
        }

        // 加入后面的
        ret.append(nums[n-1] + ")");

        // 返回结果
        return ret.toString();
    }
}





// 注意类名必须为 Main, 不要有任何 package xxx 信息
 class Main2 {
    public static void main(String[] args) {

        // 输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), maxV = in.nextInt();
        int[] height = new int[n + 1];
        int[] V = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            V[i] = in.nextInt();
            height[i] = in.nextInt();
        }

        // 创建 dp 表
        int[][] dp = new int[n + 1][maxV + 1];


        // 当 <= j  的情况
        // 进行状态转移
        for (int i = 1; i <= n ; i++) {
            // 这里的j 表示当前位置下的最大的体积
            // dp[i][j] 就表示 height[i] 位置下的  <= j 体积的最大重量
            for (int j = 1; j <= maxV; j++) {
                // 分情况讨论, 分别得到 当前位置是否需要加入
                // 先更新当前位置不加入的情况
                dp[i][j] = dp[i - 1][j];


                // 只有当前位置还能装下就更新 dp
                if (j - V[i] >= 0) {
                    // 两种情况取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - V[i]] + height[i]);
                }

            }
        }

        System.out.println(dp[n][maxV]);


        dp = new int[n + 1][maxV + 1];


        // 初始化
        for(int j = 1 ; j <= maxV ; j++) {
            // 表示当前位置不能填
            // 只有体积没有重量
            dp[0][j] = -1;
        }


        // 当 <= j  的情况
        // 进行状态转移
        for (int i = 1; i <= n ; i++) {
            // 这里的j 表示当前位置下的最大的体积
            // dp[i][j] 就表示 height[i] 位置下的  <= j 体积的最大价值
            for (int j = 1; j <= maxV; j++) {
                // 分情况讨论, 分别得到 当前位置是否需要加入
                // 先更新当前位置不加入的情况
                dp[i][j] = dp[i - 1][j];
                // 只有当前位置还能装下就更新 dp
                if (j - V[i] >= 0 && dp[i - 1][j - V[i]]  != -1) {

                    // 两种情况取最大值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - V[i]] + height[i]);
                }
            }
        }

        System.out.println(dp[n][maxV] > 0  ? dp[n][maxV] : 0);

    }
}


/**
 * 题目: 动态规划_粉刷房子
 */


class Solution4 {
    public int minCost(int[][] costs) {
        int n = costs.length ;
        int[][] dp = new int[n][3];

        // 进行初始化
        for(int i = 0; i < 3; i++) {
            dp[0][i] = costs[0][i];
        }


        for(int i = 1; i < n; i++) {

            // 当前位置要选
            dp[i][0] = Math.min(dp[i-1][1] +  costs[i][0], dp[i-1][2] +  costs[i][0]) ;

            // 当前位置要选
            dp[i][1] = Math.min(dp[i-1][2] +  costs[i][1], dp[i-1][0] +  costs[i][1]) ;

            // 当前位置要选
            dp[i][2] = Math.min(dp[i-1][0] +  costs[i][2], dp[i-1][1] +  costs[i][2]) ;

        }


        int ret = Integer.MAX_VALUE;
        // 寻找最小值
        for(int i = 0; i < 3; i++) {
            ret = Math.min(dp[n-1][i], ret);
        }

        return ret;
    }
}